// 2025/3/5
// https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked
// 除自身以外数组的乘积

class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n = nums.size();
            vector<int> prev(n, 1), back(n, 1);
            for(int i = 1; i < n; i++)
            {
                prev[i] = prev[i - 1] * nums[i - 1];
                int j = n - 1 - i;
                back[j] = back[j + 1] * nums[j + 1];
            }
    
            vector<int> answer(n, 1);
            for(int i = 0; i < n; i++)
            {
                answer[i] = prev[i] * back[i];
            }
            return answer;
        }
    };

// 双指针，效率和空间复杂度都更优
class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n = nums.size();
            vector<int> answer(n, 1);
            int left = 0, right = n - 1;
            int lm = 1, rm = 1;
            while(left < n && right >= 0)
            {
                answer[left] *= lm;
                answer[right] *= rm;
                lm *= nums[left++];
                rm *= nums[right--];
            }
            return answer;
        }
    };